Minimum Knight Moves

Understand and solve the interview question "Minimum Knight Moves".

Description#

We have an infinite chessboard with coordinates starting from -infinity to infinity. Our knight starts in square (0, 0).

The knight has eight possible moves at a given time. It can move in an L-shape, meaning it can move two squares in any direction vertically and then one square horizontally or two squares in any direction horizontally and then one square vertically.

You need to find the minimum moves the knight needs to get from the origin (0,0) to the coordinates (x,y). We will assume that the provided coordinates are always reachable and the constraint |x| + |y| <= 300 holds.

For example, given the input coordinate, (5, 5) you have to find the minimum number of moves required for the knight to get from the origin to the coordinate. In this case, the program will output four because the knight needs four moves to get to the coordinate.

Created with Fabric.js 3.6.3 Knight at (0, 0) 2, -2 1, -2 0, -2 -1, -2 -2, -2 2, -1 1, -1 0, -1 -1, -1 -2, -1 2, 0 1, 0 0, 0 -1, 0 -2, 0 2, 1 1, 1 0,1 -1, 1 -2, 1 2, 2 1, 2 0, 2 -1, 2 -2, 2
Chess Board

1 of 2

Created with Fabric.js 3.6.3 2, -2 1, -2 0, -2 -1, -2 -2, -2 2, -1 1, -1 0, -1 -1, -1 -2, -1 2, 0 1, 0 0, 0 -1, 0 -2, 0 2, 1 1, 1 0,1 -1, 1 -2, 1 2, 2 1, 2 0, 2 -1, 2 -2, 2 Initial Possible Moves
Initial Possible Moves

2 of 2

Coding exercise#

Minimum Knight Moves

Solution#

Notice that the knight’s movements to both the positive and negative coordinates and the axis are symmetrical. The same number of moves are required to get to both the positive and negative coordinates. The knight can move in any of the eight directions at any given time by adding the following coordinates, [{1, 2}, {2, 1}, {-1, 2}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {2, -1}] to the current coordinates.

Therefore, we can avoid the negative coordinates and create our solution around the first quadrant, keeping the coordinates positive. The origin is fixed, and we can use this to transform our input coordinates. We can take the absolute value of the coordinate and use it as our starting point. This way, we know which direction we should move in. In this case, we will only move in two directions by adding the following coordinates to the current coordinates, [{-1, -2}, {-2, -1}]. We will only explore the absolute values of the coordinates.

Here is how we will implement this solution:

  1. Take the absolute values of the coordinates (x, y).
  2. Manually initialize the map with the minimum moves it takes to get to the origin’s coordinates. The map contains the coordinate as the key and minimum knight it takes to get to the origin as the value.
  3. Start from the input coordinates and explore all the squares in a depth-first manner back to the origin.
  4. If the coordinate has already been explored, we can return that value; otherwise, we will explore the next possible coordinates the knight can move to.
  5. We pick the path with the minimum moves and backtrack to the input coordinate.
Created with Fabric.js 3.6.3 Knight at (0, 0) 5, 0 4, 0 3, 0 2, 0 1, 0 0, 0 5, 1 4, 1 3, 1 2, 1 1, 1 0, 1 5, 2 4, 2 3, 2 2, 2 1, 2 0, 2 5, 3 4, 3 3, 3 2, 3 1, 3 0, 3 5, 4 4, 4 3, 4 2, 4 1, 4 0, 4 5, 5 4, 5 3, 5 2, 5 1, 5 0, 5 1, 0 3 0, 1 3 2, 0 2 0, 2 2 1, 1 2 0, 0 0 Initial Map
Chess Board

1 of 12

Created with Fabric.js 3.6.3 1, 0 3 0, 1 3 2, 0 2 0, 2 2 1, 1 2 0, 0 0 Initial Map Initial Coordinate (5, 5) 5, 0 4, 0 3, 0 2, 0 1, 0 0, 0 5, 1 4, 1 3, 1 2, 1 1, 1 0, 1 5, 2 4, 2 3, 2 2, 2 1, 2 0, 2 5, 3 4, 3 3, 3 2, 3 1, 3 0, 3 5, 4 4, 4 3, 4 2, 4 1, 4 0, 4 5, 5 4, 5 3, 5 2, 5 1, 5 0, 5
Initial Coordinate

2 of 12

Created with Fabric.js 3.6.3 1, 0 3 0, 1 3 2, 0 2 0, 2 2 1, 1 2 0, 0 0 Initial Map Possible Moves 5, 0 4, 0 3, 0 2, 0 1, 0 0, 0 5, 1 4, 1 3, 1 2, 1 1, 1 0, 1 5, 2 4, 2 3, 2 2, 2 1, 2 0, 2 5, 3 4, 3 3, 3 2, 3 1, 3 0, 3 5, 4 4, 4 3, 4 2, 4 1, 4 0, 4 5, 5 4, 5 3, 5 2, 5 1, 5 0, 5 The coordinate (5, 5) does not exist in the HashMap. So, we explore the next possible coordinates, (4, 3) and (3, 4).
Possible Moves

3 of 12

Created with Fabric.js 3.6.3 1, 0 3 0, 1 3 2, 0 2 0, 2 2 1, 1 2 0, 0 0 Initial Map Explore Coordinate (3, 4) 5, 0 4, 0 3, 0 2, 0 1, 0 0, 0 5, 1 4, 1 3, 1 2, 1 1, 1 0, 1 5, 2 4, 2 3, 2 2, 2 1, 2 0, 2 5, 3 4, 3 3, 3 2, 3 1, 3 0, 3 5, 4 4, 4 3, 4 2, 4 1, 4 0, 4 5, 5 4, 5 3, 5 2, 5 1, 5 0, 5 Coordinate (3, 4) does not exist in the map either.So, we will check the next two possible coordinates, (1,3) and (2, 2).
Explore Coordinate (3, 4)

4 of 12

Created with Fabric.js 3.6.3 1, 0 3 0, 1 3 2, 0 2 0, 2 2 1, 1 2 0, 0 0 Initial Map Explore Coordinate (1, 3) 5, 0 4, 0 3, 0 2, 0 1, 0 0, 0 5, 1 4, 1 3, 1 2, 1 1, 1 0, 1 5, 2 4, 2 3, 2 2, 2 1, 2 0, 2 5, 3 4, 3 3, 3 2, 3 1, 3 0, 3 5, 4 4, 4 3, 4 2, 4 1, 4 0, 4 5, 5 4, 5 3, 5 2, 5 1, 5 0, 5 Coordinate (1, 3) does not exist in the map either.So, we will check the next two possible coordinates, (|-1|,|2|) and (|0|, |1|).
Explore Coordinate (1, 3)

5 of 12

Created with Fabric.js 3.6.3 Updated Map Explore Coordinate (1, 2) 5, 0 4, 0 3, 0 2, 0 1, 0 0, 0 5, 1 4, 1 3, 1 2, 1 1, 1 0, 1 5, 2 4, 2 3, 2 2, 2 1, 2 0, 2 5, 3 4, 3 3, 3 2, 3 1, 3 0, 3 5, 4 4, 4 3, 4 2, 4 1, 4 0, 4 5, 5 4, 5 3, 5 2, 5 1, 5 0, 5 1, 0 3 0, 1 3 2, 0 2 0, 2 2 1, 1 2 0, 0 0 Coordinate (0, 1) exists in the map.But the (1, 2) coordinate does not exist in the map. We explore the coordinates (0, 0) and (|-1|, |1|).
Explore Coordinate (1, 2)

6 of 12

Created with Fabric.js 3.6.3 Updated Map 5, 0 4, 0 3, 0 2, 0 1, 0 0, 0 5, 1 4, 1 3, 1 2, 1 1, 1 0, 1 5, 2 4, 2 3, 2 2, 2 1, 2 0, 2 5, 3 4, 3 3, 3 2, 3 1, 3 0, 3 5, 4 4, 4 3, 4 2, 4 1, 4 0, 4 5, 5 4, 5 3, 5 2, 5 1, 5 0, 5 1, 2 1 1, 0 3 0, 1 3 2, 0 2 0, 2 2 1, 1 2 0, 0 0 Update Coordinate (1, 2) The coordinates (0, 0) and (1,1) exist in the map.We set the map for (1, 2) with the 1 + minimum of dfs(|0|, |0|) and dfs(|-1|, |1|) and start backtracking.
Explore Coordinate (1, 2)

7 of 12

Created with Fabric.js 3.6.3 Update Coordinate (1, 3) Updated Map 1, 3 2 1, 2 1 1, 0 3 0, 1 3 2, 0 2 0, 2 2 1, 1 2 0, 0 0 5, 0 4, 0 3, 0 2, 0 1, 0 0, 0 5, 1 4, 1 3, 1 2, 1 1, 1 0, 1 5, 2 4, 2 3, 2 2, 2 1, 2 0, 2 5, 3 4, 3 3, 3 2, 3 1, 3 0, 3 5, 4 4, 4 3, 4 2, 4 1, 4 0, 4 5, 5 4, 5 3, 5 2, 5 1, 5 0, 5 Both coordinates (0, 1) and (1, 2) exist in the map.We will update the (1, 3) coordinateand set the map with the 1 + minimum of dfs(|1|, |2|) and dfs(|0|, |1|).
Update Coordinate (1, 3)

8 of 12

Created with Fabric.js 3.6.3 Updated Map 5, 0 4, 0 3, 0 2, 0 1, 0 0, 0 5, 1 4, 1 3, 1 2, 1 1, 1 0, 1 5, 2 4, 2 3, 2 2, 2 1, 2 0, 2 5, 3 4, 3 3, 3 2, 3 1, 3 0, 3 5, 4 4, 4 3, 4 2, 4 1, 4 0, 4 5, 5 4, 5 3, 5 2, 5 1, 5 0, 5 Explore Coordinate (2, 2) 2, 2 4 1, 3 2 1, 2 1 1, 0 3 0, 1 3 2, 0 2 0, 2 2 1, 1 2 Coordinate (2, 2) does not exist in the map.We will update the (2, 2) coordinateand set the map with the 1 + minimum of dfs(|0|, |1|) and dfs(|1|, |0|) as both already exist in the map.
Explore Coordinate (2, 2)

9 of 12

Created with Fabric.js 3.6.3 Updated Map Update Coordinate (3, 4) 5, 0 4, 0 3, 0 2, 0 1, 0 0, 0 5, 1 4, 1 3, 1 2, 1 1, 1 0, 1 5, 2 4, 2 3, 2 2, 2 1, 2 0, 2 5, 3 4, 3 3, 3 2, 3 1, 3 0, 3 5, 4 4, 4 3, 4 2, 4 1, 4 0, 4 5, 5 4, 5 3, 5 2, 5 1, 5 0, 5 3, 4 3 2, 2 4 1, 3 2 1, 2 1 1, 0 3 0, 1 3 2, 0 2 0, 2 2 Coordinate (2, 2) does not exist in the map.We will update the (2, 2) coordinateand set the map with the 1 + minimum of dfs(|0|, |1|) and dfs(|1|, |0|) because both already exist in the map.
Update Coordinate (3, 4)

10 of 12

Created with Fabric.js 3.6.3 Updated Map Explore Coordinate (4, 3) 5, 0 4, 0 3, 0 2, 0 1, 0 0, 0 5, 1 4, 1 3, 1 2, 1 1, 1 0, 1 5, 2 4, 2 3, 2 2, 2 1, 2 0, 2 5, 3 4, 3 3, 3 2, 3 1, 3 0, 3 5, 4 4, 4 3, 4 2, 4 1, 4 0, 4 5, 5 4, 5 3, 5 2, 5 1, 5 0, 5 4, 3 3 3, 4 3 2, 2 4 1, 3 2 1, 2 1 1, 0 3 0, 1 3 2, 0 2 Because of the symmetrical nature of the problem, we can use the same moves to get to (4, 3) as (3, 4), which we have already explored.
Explore Coordinate (4, 3)

11 of 12

Created with Fabric.js 3.6.3 Updated Map Update Coordinate (5, 5) 5, 0 4, 0 3, 0 2, 0 1, 0 0, 0 5, 1 4, 1 3, 1 2, 1 1, 1 0, 1 5, 2 4, 2 3, 2 2, 2 1, 2 0, 2 5, 3 4, 3 3, 3 2, 3 1, 3 0, 3 5, 4 4, 4 3, 4 2, 4 1, 4 0, 4 5, 5 4, 5 3, 5 2, 5 1, 5 0, 5 5, 5 4 4, 3 3 3, 4 3 2, 2 4 1, 3 2 1, 2 1 1, 0 3 0, 1 3 We will set the value for coordinate (5, 5) with the 1 + minimum of the dfs(4, 3) and dfs(3, 4).Finally, we have the moves(4) it requires for the knightto get to (5, 5) from the origin(0, 0).
Update Coordinate (5, 5)

12 of 12

Let’s review the solution:

Minimum Knight Moves

Complexity measures#

Time complexity Space complexity
O(xy)O(\|x\| * \|y\|) O(xy)O(\|x\| * \|y\|)

Time complexity#

We are dealing with a submatrix starting from the origin and ending at [x, y]. The origin is fixed, and we might have to traverse all the squares. Therefore, the time complexity will be O(xy)O(\|x\| * \|y\|).

Space complexity#

We might have to store the moves for all the squares, so the space complexity will be quadratic as well.

Flatten Binary Tree to Linked List

Sparse Matrix Multiplication